import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:快速排序
 * 时间复杂度:O(nlogn)
 * 空间复杂度:O(logn)
 * 稳定性: 不稳定
 * User: 86183
 * Date: 2023-05-04
 * Time: 14:21
 */
public class sortDeom7 {
    public static void main(String[] args) {
        int[] a = {67,34,12,21,45,13};
//        quickSort(a);
        quickSort1(a);
        System.out.println(Arrays.toString(a));
    }

    private static void quickSort1(int[] a) {
        quick1(a,0,a.length-1);
    }

    private static void quick1(int[] a, int start, int end) {
        if (start >= end){
            return;
        }
        int poviot = partition1(a,start,end);
        quick1(a,start,poviot-1);
        quick1(a,poviot+1,end);
    }

    private static int partition1(int[] a, int start, int end) {
        int i = start;
        int poviot = a[start];
        while (start < end){
            while (start < end && a[end] >= poviot){
                end--;
            }
            while (start < end && a[start] <= poviot){
                start++;
            }
            sortDeom5.swap(a,start,end);
        }
        sortDeom5.swap(a,i,start);
        return start;
    }

//    private static void quickSort(int[] a) {
//        quick(a,0,a.length - 1);
//    }
//
//    private static void quick(int[] a, int start, int end) {
//        //大于号:防止没有左树/右树
//        if(start >= end){
//            return;
//        }
//        int pivot = partition(a,start,end);
//        quick(a,start,pivot - 1);
//        quick(a,pivot + 1,end);
//    }
//
//    private static int partition(int[] a, int start, int end) {
//        int i = start;
//        int piovt = a[start];
//        while (start < end){
//            //必须走右边:如果走左边,相遇之后的数据,可能比基准大
//            //取等:防止陷入循环
//            while (start < end && a[end] >= piovt){
//                end --;
//            }
//            while (start < end && a[start] <= piovt){
//                start++;
//            }
//            sortDeom5.swap(a,start,end);
//        }
//        sortDeom5.swap(a,i,start);
//        return start;
//    }
}
